competitive programming

Competitive Programming(CP) 指竞赛性编程。与面向工程的程序设计不同，CP追求的是在一定的时间内，实现一定的算法和数据结构，以解决某一特定的、可能并不具有现实意义的问题。
定义来源于 CP Wiki

基础

• [[二分搜索]]

  • 它的基本思想是，对于一个在某种意义上有序的数组，这个数组的前半部分满足某一条件，而后半部分不满足这一条件，我们不断选择区间中点，判断其是否满足条件，从而将区间不断折半，最后就可以找到数组中的转折点，也即满足这一条件的最后一个点，或不满足这个条件的第一个点。

• [[三分搜索]]

  • 三分查找则是针对数组或范围满足单峰或单谷的特性，即可能是先递增后递减，或先递减后递增。

数学

• [[Number Theory]]

  • [[欧几里得算法]]

  • [[费马小定理]]

  • [[乘法逆元]]

• [[组合数学]]

字符串

• [[Manacher Algorithm]]

[[Dynamic Programming]]

• [[区间 DP]]

• [[树形 DP]]

• [[状压 DP]]

[[Graph Theory]]

[[Data structure]]

• [[差分数组]]

See Also

• [[LeetCode]]

Ref

• 整数数列线上大全 (oeis.org)

• Tutorial A way to Practice Competitive Programming : From Rating 1000 to 2400+ - Codeforces

• CP Wiki (cp-wiki.vercel.app)

• CF(codeforces)如何保持紫名及以上？ - 知乎 (zhihu.com)

  • Constructive Algorithms Problemset